package com.leetcode;

/**
 * 33 搜索旋转排序数数组
 * <p>
 * 时间复杂度 log(n)   采用二分
 * <p>
 * <p>
 * 4,5,6,7,0,1,2   target = 2
 * <p>
 * len = 7
 * i = 0
 * 4 > 2
 * <p>
 * i = 7-1 /2 = 3
 * 7 > 2
 * <p>
 * i = (7-3)/2 + 3 = 5
 * 1<2
 * <p>
 * i = (7-5)/2 + 5 = 6
 * 2 = 2
 */

public class D_33 {
    public static void main(String[] args) {
        int[] nums = {6, 7, 8, 9, 1, 2, 3, 4, 5};
//        int[] nums = {1};
//        int[] nums = {3, 1};
//        System.out.println(erfen(nums, 0, nums.length - 1, 1));
//        System.out.println(erfen(nums, 0, nums.length - 1, 2));
//        System.out.println(erfen(nums, 0, nums.length - 1, 3));
//        System.out.println(erfen(nums, 0, nums.length - 1, 4));
//        System.out.println(erfen(nums, 0, nums.length - 1, 5));
//        System.out.println(erfen(nums, 0, nums.length - 1, 6));
//        System.out.println(erfen(nums, 0, nums.length - 1, 7));
//        System.out.println(erfen(nums, 0, nums.length - 1, 8));
//        System.out.println(erfen(nums, 0, nums.length - 1, 9));
//        System.out.println(erfen(nums, 0, nums.length - 1, 10));
//
//
//
        System.out.println(new D_33().search(nums, 3));
        System.out.println(new D_33().search(nums, 2));
        System.out.println(new D_33().search(nums, 3));
        System.out.println(new D_33().search(nums, 4));
        System.out.println(new D_33().search(nums, 5));
        System.out.println(new D_33().search(nums, 6));
        System.out.println(new D_33().search(nums, 7));
        System.out.println(new D_33().search(nums, 8));
        System.out.println(new D_33().search(nums, 9));
        System.out.println(new D_33().search(nums, 10));
    }

    public int search(int[] nums, int target) {
        if (nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            }
//            左边有序
            if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
//                在左边
            } else {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }


    public static int erfen(int[] nums, int left, int right, int target) {
        int mid = (left + right) / 2;
        if (left > right) {
            return -1;
        }
        if (nums[mid] < target) {
            left = mid + 1;
            mid = (right + left) / 2;
            return erfen(nums, left, right, target);
        } else if (nums[mid] > target) {
            right = mid - 1;
            mid = (right + left) / 2;
            return erfen(nums, left, right, target);
        }
        return mid;
    }


    public int search1(int[] nums, int target) {
        int len = nums.length - 1;
        int left = 0;
        int right = len;
        int mid = (right + left) / 2;
        if (left == right && nums[left] == target) {
            return 0;
        }

        while (left <= right) {
            //            左边无序 右边有序
            if (nums[left] > nums[mid]) {
                if (nums[mid] <= target && nums[right] >= target) {
                    return erfen(nums, mid, right, target);
                }
                right = mid - 1;
                mid = (right + left) / 2;
            } else if (nums[mid] > nums[right]) {
                if (nums[left] <= target && nums[mid] >= target) {
                    return erfen(nums, left, mid, target);
                }
                left = mid + 1;
                mid = (right + mid) / 2;
            } else if (nums[mid] < nums[right]) {

                if (nums[left] <= target && nums[mid] >= target) {
                    return erfen(nums, left, mid, target);
                }
                left = mid + 1;
                mid = (right + mid) / 2;


                if (nums[mid] <= target && nums[right] >= target) {
                    return erfen(nums, mid, right, target);
                }
                right = mid - 1;
                mid = (right + left) / 2;
            }
        }
        return -1;
    }
}
